import javax.xml.stream.events.StartDocument;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-28
 * Time: 22:35
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}


public class Solution {
    public int index;

    /**
     *  构造二叉树
     * @param pre 前序
     * @param vin 中序
     * @param begin
     * @param end
     * @return
     */
    public TreeNode inorder(int [] pre, int [] vin, int begin, int end){
        if(index >= pre.length || begin > end){
            return null;
        }
        TreeNode root = new TreeNode(pre[index]);
        int mid = begin;
        for (int i = begin; i <= end ; i++) {
            if(vin[i] == pre[index]){
                // 找到了根节点, 那么左边的就是左子树, 右边的就是右子树
                mid = i;
                break;
            }
        }
        index++;
        // 构建左子树
        root.left = inorder(pre, vin, begin, mid-1);
        // 构建右子树
        root.right = inorder(pre, vin, mid+1, end);
        return root;
    }

    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        if(pre == null || vin == null || pre.length != vin.length){
            return null;
        }
        return inorder(pre, vin, 0, vin.length);
    }


}
